package buildTree;

import util.ListNode;
import util.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @program: javase
 * @description: 通过数组，生成一个二叉搜索树
 * @author: luolidong
 * @create: 2021-06-15 21:09
 * @version: 1.0
 */
public class BuildSortTreeByArray {
//    1 2 3 4 5 6 7 8 9

    /**
     * @description 构造普通二叉平衡树
     * @param root
     * @param num
     * @return util.TreeNode
     */
    public static TreeNode buildSortedTree(TreeNode root, int num) {
        if (root == null) {
            root = new TreeNode(num);
            return root;
        } else {
            if (root.val >= num) {
                root.left = buildSortedTree(root.left, num);
            } else {
                root.right = buildSortedTree(root.right, num);
            }
        }
        return root;
    }

    /**
     * @Description: 构造二叉平衡排序树
     * @Param: [arr, left, right]
     * @return: util.TreeNode
     */
    public static TreeNode buildMinHeightTree(int[] arr, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(arr[mid]);
        node.left = buildMinHeightTree(arr, left, mid - 1);
        node.right = buildMinHeightTree(arr, mid + 1, right);
        return node;
    }

    /**
     * @Description: 二叉排序树中序遍历必是有序的
     * @Param: [root, list]
     * @return: java.util.List<java.lang.Integer>
     */
    public static List<Integer> midOrder(TreeNode root, List<Integer> list) {
        if (root == null) return null;
        if (root.left != null) midOrder(root.left, list);
        list.add(root.val);
        if (root.right != null) midOrder(root.right, list);
        return list;
    }
    /**
    * @Description: 找链表中点
    * @Param: [left, right]
    * @return: util.ListNode
    */
    public static ListNode getMid(ListNode left, ListNode right){
        ListNode fast=left;
        ListNode slow=left;
        while(fast!=right&&fast.next!=right){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] split = s.split(",");
        int[] arr = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }
//        TreeNode root=new TreeNode(arr[0]);
//        for (int i = 1; i < arr.length ; i++) {
//            buildSortedTree(root, arr[i]);
//        }
////        中序遍历
//        List<Integer> list = midOrder(root, new ArrayList<>());
//        System.out.println(list);

//        构造二叉平衡排序树
        Arrays.sort(arr);
        TreeNode treeNode = buildMinHeightTree(arr, 0, arr.length - 1);
        ////        中序遍历
        List<Integer> list = midOrder(treeNode, new ArrayList<>());
        System.out.println(list);

        ListNode mid = getMid(ListNode.build(), null);
        System.out.println(mid);

    }

}
